/*
 * @lc app=leetcode.cn id=47 lang=cpp
 *
 * [47] 全排列 II
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    set<string> ans;

    void dfs(string& nums, int inx)
    {
        if(inx == nums.size() - 1)
        {
            ans.insert(nums);
            return;
        }
        for(int i = inx; i < nums.size(); i++)
        {
            swap(nums[i], nums[inx]);
            dfs(nums, inx + 1);
            swap(nums[i], nums[inx]);
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        
        string new_nums;
        for(auto& n : nums)
        {
            new_nums += n + 'a';
        }

        dfs(new_nums, 0);

        vector<vector<int>> res;
        for(auto& item: ans)
        {
            vector<int> tmp;
            for(int i = 0; i < item.size(); i++)
            {
                tmp.push_back(item[i] - 'a');
            }
            res.push_back(tmp);
        }
        return res;
    }
};
// @lc code=end

